// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-24 14:46
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Graph.Dijkstra.DijistraT;

import org.junit.jupiter.api.Test;

import java.util.LinkedList;

@SuppressWarnings("ALL")
public class Graph {

    private class Edge {// 表示边
        public int sid;// 边的起始节点
        public int tid;// 边的结束节点
        public int w;// 边的权重

        public Edge(int s, int t, int w) {
            this.sid = s;
            this.tid = t;
            this.w = w;
        }
    }

    public class Vertex {// 用于算法实现中，记录第一个节点到这个节点的距离
        public int id;
        public int dist;

        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }

    // 邻接表
    private LinkedList<Edge> adj[];
    // 顶点数
    private int v;

    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            /*-----初始化邻接链表-----*/
            this.adj[i] = new LinkedList<Edge>();
        }
    }

    public void addEdge(int s, int t, int w) {
        this.adj[s].add(new Edge(s, t, w));
    }


    /**
     * 计算从顶点 s 到 t 的最短路
     *
     * @param s
     * @param t
     */
    public void dijkstra(int s, int t) {
        // 用于还原最短路的路径
        int[] pre = new int[this.v + 1];
        Vertex[] vertexes = new Vertex[this.v + 1];
        //初始化 vertexes 数组
        for (int i = 0; i < this.v; i++) {
            /*-----初始节点距离为无穷远-----*/
            vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
        }
        //小顶堆
        PriorityQueue queue = new PriorityQueue(this.v + 1);
        //标记节点是否已经入队
        boolean[] inqueue = new boolean[this.v + 1];

        vertexes[s].dist = 0;
        queue.add(vertexes[s]);
        inqueue[s] = true;

        while (!queue.isEmpty()) {
            Vertex minVertex = queue.poll();
            if (minVertex.id == t) {
                break;
            }

            for (int i = 0; i < this.adj[minVertex.id].size(); i++) {//遍历节点连通的其他节点
                Edge e = this.adj[minVertex.id].get(i);//取出节点 minVertex.id 相连的节点
                Vertex nextVertex = vertexes[e.tid];//初始节点到下一个节点的距离
                if (minVertex.dist + e.w < nextVertex.dist) {//上一步计算得到的距离和当前计算出的距离比较
                    nextVertex.dist = minVertex.dist + e.w;//更新距离
                    pre[nextVertex.id] = minVertex.id;//记录路径
                    if (inqueue[nextVertex.id]) {//若节点已经在队列中，则更新值，若不在则入队
                        queue.update(nextVertex);
                    } else {
                        queue.add(nextVertex);
                        inqueue[nextVertex.id] = true;
                    }
                }
            }
        }
        System.out.print(s);
        print(s, t, pre);
    }

    private void print(int s, int t, int[] pre) {
        if (s == t) return;
        print(s, pre[t], pre);
        System.out.print("->" + t);
    }


    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(1, 2, 1);
        g.addEdge(1, 3, 12);
        g.addEdge(2, 4, 3);
        g.addEdge(2, 3, 9);
        g.addEdge(4, 3, 4);
        g.addEdge(4, 5, 13);
        g.addEdge(3, 5, 5);
        g.addEdge(5, 6, 4);
        g.addEdge(4, 6, 15);
        g.dijkstra(1, 5);
    }
/*output:
1->2->4->3->5->6
*/


}

